package chapter02;

import java.util.Arrays;

public class MinPathSum64 {
    /**
     * 记忆化搜索
     * 递归出口
     *  1)x==grid.length||y==grid[0].length
     *    return max_value
     *  2)x==grid.length-1&&y==grid[0].length-1
     *    return grid[x][y]
     *  3)没有出局 返回后续结果
     *    return grid[x][y]+Math.min(process(x+1,y)+process(x,y+1))
     *  有些位置(x,y)会反复方便 增加一个dp[x][y]缓存该位置返回结果 节约时间
     *  动态规划
     *  根据递归改动态规划
     */
    //记忆化搜索
    public int minPathSum(int[][] grid) {
        int[][] dp=new int[grid.length+1][grid[0].length+1];
        for(int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],-1);
        }
        return process(0,0,grid,dp);
    }

    public int process(int x,int y,int[][] grid,int[][] dp){
        if(dp[x][y]!=-1){
            return dp[x][y];
        }
        if(x==grid.length||y==grid[0].length){
            dp[x][y]=Integer.MAX_VALUE;
            return dp[x][y];
        }
        if(x==grid.length-1&&y==grid[0].length-1){
            dp[x][y]=grid[x][y];
            return dp[x][y];
        }
        dp[x][y]=grid[x][y]+Math.min(process(x+1,y,grid,dp),process(x,y+1,grid,dp));
        return dp[x][y];
    }

    //动态规划
    public int minPathSum1(int[][] grid){
        int[][] dp=new int[grid.length+1][grid[0].length+1];
        dp[dp.length-2][dp[0].length-2]=grid[dp.length-2][dp[0].length-2];
        for(int j=0;j<dp[0].length;j++){
            dp[dp.length-1][j]=Integer.MAX_VALUE;
        }
        for(int i=0;i<dp.length;i++){
            dp[i][dp[0].length-1]=Integer.MAX_VALUE;
        }
        for(int j=dp[0].length-3;j>=0;j--){
            dp[dp.length-2][j]=grid[dp.length-2][j]+Math.min(dp[dp.length-1][j],dp[dp.length-2][j+1]);
        }
        for(int i=dp.length-3;i>=0;i--){
            for(int j=dp[0].length-2;j>=0;j--){
                dp[i][j]=grid[i][j]+Math.min(dp[i+1][j],dp[i][j+1]);
            }
        }
        return dp[0][0];
    }
}
